import java.util.*;

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> cnt = new HashMap<String, Integer>();
        for (String word : words) {
            cnt.put(word, cnt.getOrDefault(word, 0) + 1);
        }

        PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<Map.Entry<String, Integer>>(new Comparator<Map.Entry<String, Integer>>() {
            public int compare(Map.Entry<String, Integer> entry1, Map.Entry<String, Integer> entry2) {
                return entry1.getValue() == entry2.getValue() ? entry2.getKey().compareTo(entry1.getKey()) : entry1.getValue() - entry2.getValue();
            }
        });
        for (Map.Entry<String, Integer> entry : cnt.entrySet()) {
            pq.offer(entry);
            if (pq.size() > k) {
                pq.poll();
            }
        }
        List<String> ret = new ArrayList<String>();
        while (!pq.isEmpty()) {
            ret.add(pq.poll().getKey());
        }
        Collections.reverse(ret);
        return ret;
    }
}



public class Test
{
    public static int maxSumDivThree(int[] nums) {
        int sum = 0, max = 0xffff;
       PriorityQueue<Integer> q = new PriorityQueue<Integer>((a,b)-> {
            return a - b;
        });
        PriorityQueue<Integer> q1 = new PriorityQueue<Integer>((a,b)-> {
            return a - b;
        });
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (nums[i] % 3 == 1)
                q.add(nums[i]);
            if (nums[i] % 3 == 2)
                q1.add(nums[i]);
        }
        if (sum % 3 == 0)
            return sum;
        int x1 = 0xffff, x2 = 0xffff;
        if (!q.isEmpty())
            x1 = q.poll();
        if (!q.isEmpty())
            x2 = q.poll();
        int y1 = 0xffff, y2 = 0xffff;
        if (!q1.isEmpty())
            y1 = q1.poll();
        if (!q1.isEmpty())
            y2 = q1.poll();
        if(sum%3==1) return Math.max(sum-x1,sum-y1-y2);
        else return Math.max(sum-y1,sum-x1-x2);
    }
    public static int jewelleryValue(int[][] frame) {
        int n=frame.length;
        int m=frame[0].length;
        int[][] arr=new int[n+1][m+1];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                arr[i][j]=Math.max(arr[i][j-1],arr[i-1][j])+frame[i-1][j-1];
            }
        }
        return arr[n][m];

    }
    public static boolean canPartition(int[] nums) {
        int sum=0;
        for(int i=0;i<nums.length;i++){
            sum+=nums[i];
        }
        if(sum%2!=0) return false;
        sum/=2;
        int n=nums.length;
        boolean[][] dp=new boolean[n][sum+1];
        for(int i=0;i<n;i++) dp[i][0]=true;
        for(int i=1;i<n;i++){
            for(int j=1;j<sum+1;j++){
                dp[i][j]=dp[i-1][j];
                if(j>=nums[i-1])
                    dp[i][j]=dp[i-1][j]||dp[i-1][j-nums[i-1]];
            }
        }
        return dp[n-1][sum];
    }
    public static void main(String[] args) {
        int[][] frame={{2,3,1},{1,5,1},{4,2,9}};
      int[] nums={1,2,3,5};
        System.out.println(canPartition(nums));
//    ArrayList<Integer> ret=new ArrayList<>();
//    ret.add(1);
//    ret.add(0,2);
//        System.out.println(ret.get(0));
//      StringBuffer sb = new StringBuffer();
//      sb.append("dfstag");
//        System.out.println(sb.charAt(0));
//
//        char ch=(char)(0+'a');
//        System.out.println(ch);
//        HashMap<String,Integer> hash=new HashMap<>();
//        int a=(int)Math.pow(8,0.5);
//        System.out.println(a);

    }
}
